import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: AliceMana
 * Date: 2023-01-06
 * Time: 17:45
 */
// https://leetcode.cn/problems/sort-list/submissions/
public class Solution {
    public static ListNode sortList1(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode node = new ListNode();
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });

        ListNode cur = head;
        while (cur != null) {
            queue.add(cur);
            cur = cur.next;
        }

        ListNode cur2 = node;
        if (!queue.isEmpty()) {
            cur2.val = queue.poll().val;
        }
        while (!queue.isEmpty()) {
            ListNode newNode = new ListNode(queue.poll().val);
            cur2.next = newNode;
            cur2 = cur2.next;
        }
        return node;
    }

    // 归并排序写法
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 以中间为分界断开
        ListNode middle = middleNode(head);
        ListNode rightHead = middle.next;
        middle.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

        // 合并
        return mergeTwoLists(left, right);
    }

    // 合并两个有序链表
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode node = new ListNode();
        ListNode cur = node;

        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                cur.next = new ListNode(list2.val);
                list2 = list2.next;
            } else {
                cur.next = new ListNode(list1.val);
                list1 = list1.next;
            }
            cur = cur.next;
        }

        if (list1 != null) {
            cur.next = list1;
        } else if (list2 != null) {
            cur.next = list2;
        }
        return node.next;
    }

    // 寻找链表中间节点
    public static ListNode middleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(4);
        list.addLast(2);
        list.addLast(1);
        list.addLast(3);
        ListNode head = sortList(list.head);
        System.out.println();
    }
}
